/**
 环形链表
 */

// 141. 环形链表
func hasCycle(_ head: ListNode?) -> Bool {
    if head == nil || head?.next == nil { return false }
    var slow = head, fast = head
    while fast != nil, fast != nil {
        slow = slow?.next
        fast = fast?.next?.next
        if slow === fast { return true }
    }
    return false
}

// 142. 环形链表2
func detectCycle(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil { return nil }
    var slow = head, fast = head
    while fast != nil, fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        if slow === fast {
            slow = head
            while slow !== fast {
                slow = slow?.next
                fast = fast?.next
            }
            return slow
        }
    }
    return nil
}

// 202. 快乐数
func isHappy(_ n: Int) -> Bool {
    func happyNum(_ n: Int) -> Int {
            var sum = 0, nn = n
            while nn != 0 {
                let num = nn % 10
                sum += num * num
                nn = nn / 10
            }
            return sum
        }

    if n == 0 { return false}
    var slow = n, fast = n
    while fast != 1, happyNum(fast) != 1 {
        slow = happyNum(slow)
        fast = happyNum(happyNum(fast))
        if slow == fast { return false }
    }
    return true
}

var head = ListNode(4)
head.next = ListNode(5)
// head.next?.next = head
head.next?.next = ListNode(9)
// head.next?.next?.next = head.next
head.next?.next?.next = ListNode(10)
head.next?.next?.next?.next = head.next

print(hasCycle(head))
